/*
Given two strings .Print all the interleavings of the two strings.
Interleaving means that the if B comes after A .It should also come after A in the interleaved string.
ex-
AB and CD
ABCD
ACBD
ACDB
CABD
CADB
CDAB
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void printHelper(const string &str1, int index1, const string &str2, int index2, string cur)
{
    if (index1 == str1.size() && index2 == str2.size()) {
	cout << cur << endl;
	return;
    } 

    if (index1 < str1.size())
	printHelper(str1, index1+1, str2, index2, cur + str1[index1]);

    if (index2 < str2.size())
	printHelper(str1, index1, str2, index2+1, cur + str2[index2]);
}

void printIninterleave(const char *str1, const char *str2)
{
    string cur;
    printHelper(str1, 0, str2, 0, cur);
}

int main(int argc, char **argv)
{
    printIninterleave("ab","cd");
}
